package Hard;
//42.接雨水
public class Solution42 {
    public int trap(int[] height) {
        //找到第一个不为0的数
        int i;
        for(i=0;i<height.length;i++){
            if(height[i]!=0)
                break;
        }
        if(i==height.length)
            return 0;
        int sum = 0;
        while (i<height.length){
            int j = i ;//固定左边界
            if(j==height.length-1){
                break;//如果左边界是最后一个数，则必然没有右边界
            }
            int k;     //寻找右边界，右边界height[j]要求>=height[i]
            for(k=j+1;k<height.length;k++){
                if(height[k]>=height[j])
                    break;
            }
            if(k==height.length){
                //如果没有比左边界更大的右边界，则寻找凹陷
                //如果没有凹陷，则从下一个格子开始找
                //寻找凹陷的方法：从i+1开始，找到一个a，使得[i+1,a-1)这个区域中所有数都小于a对应的数且a之后不存在比a大的数
                int a;
                for(a = i+2;a<height.length;a++){
                    if(height[a]>height[i+1])
                        break;
                }
                if(a==height.length){
                    //没有凹陷
                    i++;
                    continue;
                }

                else {
                    //继续更新右边界，寻找a后面中的最大数，如果最大数比a大，则替换，否则不替换
                    for(int b = a+1;b<height.length;b++){
                        if(height[b]>height[a])
                            a=b;
                    }
                    //有凹陷，形如[5,3,2,1,4]右边界肯定比左边界小
                    int count = a-i-1;
                    //记录凹陷处的起始坐标和终止坐标
                    int u = i+1;
                    int v = a-1;
                    //计算这个凹陷能装多少水(可存水的面积=全部面积-柱子面积)
                    int water = count*height[a];
                    for(int p = u ; p <=v ; p++){
                        water-=height[p];
                    }
                    sum+=water;
                    i=a;
                    continue;
                }
            }
            //数一下左右边界中间夹了几个数
            int count = k-j-1;
            if(count==0){
                //紧挨着的墙壁无法存水
                i++;
                continue;
            }
            //记录凹陷处的起始坐标和终止坐标
            int u = j+1;
            int v = k-1;
            //计算这个凹陷能装多少水(可存水的面积=全部面积-柱子面积)
            int water = count*height[i];
            //开始减去柱子面积
            for(int p = u ; p <=v ; p++){
                water-=height[p];
            }
            sum+=water;
            i=k;//更新新的左边界
        }
        return sum;
    }

    public static void main(String[] args) {
        Solution42 s = new Solution42();
        System.out.println(s.trap(new int[]{2,8,5,5,6,1,7,4,5}));
    }
}
